﻿//#define DEBUG_OCTREE

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace DARE
{
    public class COctreeNode : IPartitioner
    {

    #region fields

        private bool m_cleanOnRemove = true;

        private BoundingBox m_AABB;
        private int m_maxItems;
        private int m_depth;
        private int m_minDepth;

        private int m_branchPos;

        private COctreeNode m_parent;

        // references
        private COctree m_Octree;

        // local
        private COctreeNode[] m_branches;
        private Dictionary<int, IPartitionerItem> m_items;
        //private Dictionary<int, COcItem> m_items;

        // used to draw the bounding box
        private COctreeAABBModel m_aabbModel;
        private COctreeAABBModel m_itemModel;

        // debug
        private bool m_DEBUGsprite = true;

        //private float m_distFromCam;

    #endregion

    #region properties

        public List<IPartitionerItem> Regular
        {
            get { return m_Octree.Regular; }
        }

        public List<IPartitionerItem> BackToFront
        {
            get { return m_Octree.BackToFront; }
        }

        public List<IPartitionerItem> FrontToBack
        {
            get { return m_Octree.FrontToBack; }
        }

        public int RegularNumber
        {
            get { return m_Octree.RegularNumber; }
        }

        public int BackToFrontNumber
        {
            get { return m_Octree.BackToFrontNumber; }
        }

        public int FrontToBackNumber
        {
            get { return m_Octree.FrontToBackNumber; }
        }

        public bool HasBranches
        {
            get { return m_branches == null ? false : true; }
        }

        public BoundingBox AABB
        {
            get { return m_AABB; }
        }

        public float LODRange
        {
            get;
            set;
        }

        public COctreeNode[] Branches
        {
            get { return m_branches; }
        }

        public bool Empty
        {
            get { return m_items.Count == 0; }
        }

        public int BranchPos
        {
            get { return m_branchPos; }
        }

        public int Depth
        {
            get { return m_depth; }
        }

        public bool Show
        {
            get { return m_Octree.Show; }
            set { m_Octree.Show = value; }
        }

        public bool ShowItems
        {
            get { return m_Octree.ShowItems; }
            set { m_Octree.ShowItems = value; }
        }

        public FillMode ItemsFillMode
        {
            get { return m_Octree.ItemsFillMode; }
            set { m_Octree.ItemsFillMode = value; }
        }

    #endregion

    #region ctor

        public COctreeNode(float xMin, float xMax, float yMin, float yMax, float zMin, float zMax, int maxItems, int minDepth,
            COctree octree, COctreeNode parent, int depth)
            : this(xMin, xMax, yMin, yMax, zMin, zMax, maxItems, minDepth, octree, parent, depth, -1)
        {

        }

        public COctreeNode(float xMin, float xMax, float yMin, float yMax, float zMin, float zMax, int maxItems, int minDepth,
            COctree octree, COctreeNode parent)
            : this(xMin, xMax, yMin, yMax, zMin, zMax, maxItems, minDepth, octree, parent, 0, -1)
        {

        }
        public COctreeNode(float xMin, float xMax, float yMin, float yMax, float zMin, float zMax, int maxItems, int minDepth,
            COctree octree)
            : this(xMin, xMax, yMin, yMax, zMin, zMax, maxItems, minDepth, octree, null, 0, -1)
        {

        }


        public COctreeNode(float xMin, float xMax, float yMin, float yMax, float zMin, float zMax, int maxItems, int minDepth, 
            COctree octree, COctreeNode parent, int depth, int branchPos)
        {
            m_depth = depth;
            m_branchPos = branchPos;
            m_AABB = new BoundingBox(new Vector3(xMin, yMin, zMin), new Vector3(xMax, yMax, zMax));
            m_aabbModel = null;
            m_itemModel = null;
            m_parent = parent;
            m_items = new Dictionary<int, IPartitionerItem>();
            m_maxItems = maxItems;
            m_minDepth = minDepth;
            m_Octree = octree;
        }

    #endregion

    #region methods

        private void Split()
        {
            if (HasBranches)
                return;

            float xMin = m_AABB.Min.X;
            float xMax = m_AABB.Max.X;
            float yMin = m_AABB.Min.Y;
            float yMax = m_AABB.Max.Y;
            float zMin = m_AABB.Min.Z;
            float zMax = m_AABB.Max.Z;
            float xHalf = xMax - (xMax - xMin) / 2.0f;
            float yHalf = yMax - (yMax - yMin) / 2.0f;
            float zHalf = zMax - (zMax - zMin) / 2.0f;

            m_branches = new COctreeNode[8];
            
            m_branches[0] = new COctreeNode(xMin, xHalf, yMin, yHalf, zMin, zHalf, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 0); // left bottom front, LBF        
            m_branches[1] = new COctreeNode(xHalf, xMax, yMin, yHalf, zMin, zHalf, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 1); // right bottom front, RBF         
            m_branches[2] = new COctreeNode(xMin, xHalf, yHalf, yMax, zMin, zHalf, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 2); // left top front, LTF            
            m_branches[3] = new COctreeNode(xHalf, xMax, yHalf, yMax, zMin, zHalf, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 3); // right top front, RTF          
            m_branches[4] = new COctreeNode(xMin, xHalf, yMin, yHalf, zHalf, zMax, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 4); // left bottom back, LBB          
            m_branches[5] = new COctreeNode(xHalf, xMax, yMin, yHalf, zHalf, zMax, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 5); // right bottom back, RBB         
            m_branches[6] = new COctreeNode(xMin, xHalf, yHalf, yMax, zHalf, zMax, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 6); // left top back, LTB   
            m_branches[7] = new COctreeNode(xHalf, xMax, yHalf, yMax, zHalf, zMax, m_maxItems, m_minDepth, m_Octree, this, m_depth + 1, 7); // right top back, RTB 
        }

        /// <summary>
        /// Should take the camPos and boundingFrustrum because atm all the objects will be draw, 
        /// even if they are not visible.
        /// But maybe it's better to debug :)
        /// </summary>
        public void Draw()
        {
            if (HasBranches)
            {
                if (m_aabbModel == null)
                    m_aabbModel = new COctreeAABBModel(m_AABB, m_depth);
                m_aabbModel.Draw();
                foreach (COctreeNode ocNode in m_branches)
                    ocNode.Draw();
            }
            if (m_Octree.ShowItems)
            {
                // Ok but moving an object in the octree and drawing his aabb will produce lags because
                // when an object is moved, it's removed and added to the octree, so the aabb model 
                // will be rebuild.
                foreach (IPartitionerItem item in m_items.Values)
                {
                    if (item.AABBModel == null)
                        item.AABBModel = new COctreeItemModel(item.AABB);

                    BoundingBox aabb = item.AABB;
                    float x = aabb.Min.X + (aabb.Max.X - aabb.Min.X) / 2;
                    float y = aabb.Min.Y + (aabb.Max.Y - aabb.Min.Y) / 2;
                    float z = aabb.Min.Z + (aabb.Max.Z - aabb.Min.Z) / 2;

                    item.AABBModel.Draw(new Vector3(x, y, z));
                }
            }
        }

        private float BorderDistanceSquared(Vector3 point)
        {
            float xDist;
            float yDist;
            float zDist;

            if (point.X < m_AABB.Min.X)
                xDist = m_AABB.Min.X - point.X;
            else if (point.X > m_AABB.Max.X)
                xDist = m_AABB.Max.X - point.X;
            else
                xDist = 0;

            if (point.Y < m_AABB.Min.Y)
                yDist = m_AABB.Min.Y - point.Y;
            else if (point.Y > m_AABB.Max.Y)
                yDist = m_AABB.Max.Y - point.Y;
            else
                yDist = 0;

            if (point.Z < m_AABB.Min.Z)
                zDist = m_AABB.Min.Z - point.Z;
            else if (point.Z > m_AABB.Max.Z)
                zDist = m_AABB.Max.Z - point.Z;
            else
                zDist = 0;

            return xDist * xDist + yDist * yDist + zDist * zDist;
        }

        public void AddProcessItem(Vector3 camPos, IPartitionerItem item)
        {
            m_Octree.AddProcessItem(camPos, item);
        }

        private float BorderDistance(Vector3 point)
        {
            return (float)Math.Sqrt(BorderDistanceSquared(point));
        }

        public bool AddItem(IPartitionerItem item)
        {
            ContainmentType containType;
            int interChild = 0;

            // there is still some place in this node, we simply add the item
            if ((m_depth >= m_minDepth) && (m_items.Count < m_maxItems))
            {
                    m_items.Add(item.Id, item);
#if DEBUG_OCTREE
                //Console.WriteLine("level " + m_depth + " add !    => " + m_items.Count);
                CDare.Instance.DebugMgr.DebugConsole.WriteLine("[AddItem] : " + item.Id.ToString() + " at level " + m_depth + ", branch " + m_branchPos.ToString() + ", total => " + m_items.Count);
                if (m_DEBUGsprite)
                {
                    CSprite3D sprite = ((CNode)item).Entity.GetSprite3D("info");

                    if (sprite == null)
                    {
                        sprite = new DARE.CLineText3D("info");
                        sprite.Offset = Vector3.UnitY / 2;
                        ((CNode)item).Entity.AttachSprite3D(sprite);
                    }
                    if (((CLineText3D)sprite).Text == null)
                        ((CLineText3D)sprite).Text += "= " + item.Id.ToString() + " =\n" + m_depth + " c:" + m_branchPos.ToString();
                    else
                        ((CLineText3D)sprite).Text += "\n" + m_depth + " c:" + m_branchPos.ToString();
                }
#endif
                return true;
            }

            // not enough place in the node, we search for the best child node
            if (!HasBranches)
                Split();
            foreach (COctreeNode ocNode in m_branches)
            {
                containType = ocNode.AABB.Contains(item.AABB);

                // the item is entirely contained in the child node, we call back AddItem and return
                if (containType == ContainmentType.Contains) 
                {
#if DEBUG_OCTREE
                    //Console.WriteLine("level " + m_depth + " contains !");
#endif
                    ocNode.AddItem(item);
                    return true;
                }
                // the item is intersected by a child node
                else if (containType == ContainmentType.Intersects)
                {
                    // if the item is already in 4 childs nodes it means that it will be in the 8, and then take the place of the parent, 
                    // so we remove it from the childs and add it to the parent.
                    if (interChild >= 4)
                    {
#if DEBUG_OCTREE
                        //Console.WriteLine("level " + m_depth + " move item to parent !");
                        CDare.Instance.DebugMgr.DebugConsole.WriteLine("  move item " + item.Id.ToString() + " at level " + m_depth + ", branch " + m_branchPos + " to parent !");
                        if (m_DEBUGsprite)
                        {
                            CSprite3D sprite = ((CNode)item).Entity.GetSprite3D("info");

                            if (sprite == null)
                            {
                                sprite = new DARE.CLineText3D("info");
                                sprite.Offset = Vector3.UnitY / 2;
                                ((CNode)item).Entity.AttachSprite3D(sprite);
                            }
                            ((CLineText3D)sprite).Text = "moved to parent";
                            //Console.WriteLine("moved item to parent");
                        }
#endif
                        foreach (COctreeNode branch in m_branches)
                            branch.RemoveItem(item);
                        ForceAddItem(item);
                        return true;
                    }
#if DEBUG_OCTREE
                    //Console.WriteLine("level " + m_depth + " intersect !  pos = " + item.Position.ToString());
#endif
                    ocNode.ForceAddItem(item);
                    interChild += 1;
                }
            }
            return interChild != 0 ? true : false;
        }

        private bool ForceAddItem(IPartitionerItem item)
        {
            if (!m_items.ContainsKey(item.Id))
            {
                m_items.Add(item.Id, item);
#if DEBUG_OCTREE
                CDare.Instance.DebugMgr.DebugConsole.WriteLine("[ForceAddItem] : " + item.Id + " at level " + m_depth.ToString() + ", branch " + m_branchPos.ToString() + ", total => " + m_items.Count.ToString());
                //#endif
                //            }
                //#if DEBUG_OCTREE
                //Console.WriteLine("level " + m_depth + " forced add !    => " + m_items.Count.ToString() + "  pos = " + item.Position.ToString());
                if (m_DEBUGsprite)
                {
                    //CDare.Instance.DebugMgr.DebugConsole.WriteLine("level " + m_depth + " forced add !    => " + m_items.Count.ToString() + "  pos = " + item.Position.ToString());
                    CSprite3D sprite = ((CNode)item).Entity.GetSprite3D("info");

                    if (sprite == null)
                    {
                        sprite = new DARE.CLineText3D("info");
                        sprite.Offset = Vector3.UnitY / 2;
                        ((CNode)item).Entity.AttachSprite3D(sprite);
                    }
                    if (((CLineText3D)sprite).Text == null)
                        ((CLineText3D)sprite).Text += "= " + item.Id.ToString() + " =\n" + m_depth + " i:" + m_branchPos.ToString();
                    else
                        ((CLineText3D)sprite).Text += "\n" + m_depth + " i:" + m_branchPos.ToString();
                }
#endif
                return true;
            }
            return false;
        }

        public bool RemoveItem(IPartitionerItem item)
        {
            if (m_items.ContainsKey(item.Id))
            {
#if DEBUG_OCTREE
                if (m_DEBUGsprite)
                    ((CNode)item).Entity.DetachSprite3D("info");
                CDare.Instance.DebugMgr.DebugConsole.WriteLine("[RemoveItem] : " + item.Id.ToString() + " at level " + m_depth + ", branch " + m_branchPos.ToString() + ", total => " + m_items.Count.ToString());
#endif
                m_items.Remove(item.Id);
            }
            if (HasBranches)
            {
                ContainmentType containType;
                int emptyBranches = 0;

                foreach (COctreeNode branch in m_branches)
                {
                    containType = branch.AABB.Contains(item.AABB);

                    if ((containType == ContainmentType.Contains) ||
                        (containType == ContainmentType.Intersects))
                        branch.RemoveItem(item);
                    if (m_cleanOnRemove && !branch.HasBranches && branch.Empty)
                        emptyBranches += 1;
                }
                if (emptyBranches == 8) // clean the branches if it was all empty and had no sub branches
                    m_branches = null;
            }
            return true;
        }

        /// <summary>
        /// Clear the node and all his branches.
        /// </summary>
        /// <returns></returns>
        public bool Clear()
        {
#if DEBUG_OCTREE            
            //Console.WriteLine(new String(' ', m_depth * 2) + "Clear() depth " + m_depth);
#endif
            if (HasBranches)
                foreach (COctreeNode branch in m_branches)
                    branch.Clear();
            m_items.Clear();
            m_branches = null;
            return true;
        }

        private IPartitionerItem GetNearestItem(Vector3 pos, ref float shortestDist)
        {
            IPartitionerItem closest = null;
            float distance = 0;

            shortestDist = float.MaxValue;
            foreach (IPartitionerItem item in m_items.Values)
                if ((distance = Math.Abs((item.Position - pos).Length())) < shortestDist)
                {
                    closest = item;
                    shortestDist = distance;
                }
            return closest;
        }

        private COctreeNode GetNearestNode(Vector3 pos, ref float shortestDist)
        {
            COctreeNode closest = null;
            float distance = 0;

            shortestDist = float.MaxValue;
            foreach (COctreeNode branch in m_branches)
                if ((distance = Math.Abs(branch.BorderDistance(pos))) < shortestDist)
                {
                    closest = branch;
                    shortestDist = distance;
                }
            return closest;
        }

        /// <summary>
        /// Not implemented yet.
        /// Return the nearest object from the point.
        /// </summary>
        /// <param name="pos">Search postion.</param>
        /// <param name="maxDist">Maximum search range.</param>
        /// <returns>Item nearest from "pos".</returns>
        private IPartitionerItem GetItem(Vector3 pos, float maxDist)
        {
            COctreeNode closestNode = null;
            float itemDist = float.MaxValue;
            float nodeDist = float.MaxValue;

            // padding to visualize recursive level
            String strPad = new String(' ', Depth * 2);
            CDare.Instance.DebugMgr.DebugConsole.WriteLine(strPad + Depth.ToString() + ":" + m_branchPos.ToString());

            return GetNearestItem(pos, ref itemDist);
        }

        public void Process(List<CCamera> cams)
        {
            foreach (CCamera cam in cams)
            {
                Process(cam.Position, cam.Frustrum);
            }
        }

        public void Process(Vector3 pos)
        {
            float maxDist = float.MaxValue;
            IPartitionerItem item = null;
            
            item = GetItem(pos, maxDist);
        }

        public void Process(Vector3 camPos, BoundingFrustum collider)
        {
#if DEBUG_OCTREE
            //CDare.Instance.DebugMgr.DebugConsole.WriteLine(new String(' ', Depth * 2) + Depth.ToString() + ":" + m_branchPos.ToString() + " processFrustrum");
#endif
            ContainmentType containType;

            foreach (IPartitionerItem item in m_items.Values)
            {
                if (!item.IsActive)
                    continue;
                containType = collider.Contains(item.AABB);
                if ((containType == ContainmentType.Contains) ||
                    (containType == ContainmentType.Intersects))
                    m_Octree.AddProcessItem(camPos, item);
            }
            if (HasBranches)
                foreach (COctreeNode branch in m_branches)
                {
                    containType = branch.AABB.Contains(collider);
                    if ((containType == ContainmentType.Contains) || 
                        (containType == ContainmentType.Intersects))
                        branch.Process(camPos, collider);
                }
        }

        public void Process(Vector3 camPos, BoundingBox collider)
        {
#if DEBUG_OCTREE
            CDare.Instance.DebugMgr.DebugConsole.WriteLine(new String(' ', Depth * 2) + Depth.ToString() + ":" + m_branchPos.ToString() + " processBox");
#endif
            ContainmentType containType;

            foreach (IPartitionerItem item in m_items.Values)
            {
                if (!item.IsActive)
                    continue;
                containType = collider.Contains(item.AABB);
                if ((containType == ContainmentType.Contains) ||
                    (containType == ContainmentType.Intersects))
                    m_Octree.AddProcessItem(camPos, item);
            }
            if (HasBranches)
                foreach (COctreeNode branch in m_branches)
                {
                    containType = branch.AABB.Contains(collider);
                    if ((containType == ContainmentType.Contains) ||
                        (containType == ContainmentType.Intersects))
                        branch.Process(camPos, collider);
                }
        }

        public void Process(Vector3 camPos, BoundingSphere collider)
        {
#if DEBUG_OCTREE
            CDare.Instance.DebugMgr.DebugConsole.WriteLine(new String(' ', Depth * 2) + Depth.ToString() + ":" + m_branchPos.ToString() + " processSphere");
#endif
            ContainmentType containType;

            foreach (IPartitionerItem item in m_items.Values)
            {
                if (!item.IsActive)
                    continue;
                containType = collider.Contains(item.AABB);
                if ((containType == ContainmentType.Contains) ||
                    (containType == ContainmentType.Intersects))
                    m_Octree.AddProcessItem(camPos, item);
            }
            if (HasBranches)
                foreach (COctreeNode branch in m_branches)
                {
                    containType = branch.AABB.Contains(collider);
                    if ((containType == ContainmentType.Contains) || 
                        (containType == ContainmentType.Intersects))
                        branch.Process(camPos, collider);
                }
        }

    #endregion

    }
}
